/*
https://leetcode-cn.com/problems/scramble-string/solution/rao-luan-zi-fu-chuan-by-leetcode-solutio-8r9t/
 */
public class Solution87 {

    int[][][] f;
    String s1,s2;

    public boolean isScramble(String s1, String s2) {
        int l=s1.length();
        f=new int[l][l][l+1];
        this.s1=s1;
        this.s2=s2;
        return dfs(0,0,l);
    }

    private boolean dfs(int i, int j, int l) {
        if (f[i][j][l]!=0){
            return f[i][j][l]==1;
        }
        if (s1.substring(i,i+l).equals(s2.substring(j,j+l))){
            f[i][j][l]=1;
            return true;
        }
        if (!check(i,j,l)){
            f[i][j][l]=-1;
            return false;
        }
        for (int p=1;p<l;p++){
            if (dfs(i,j,p)&&dfs(i+p,j+p,l-p)||dfs(i,j+l-p,p)&&dfs(i+p,j,l-p)){
                f[i][j][l]=1;
                return true;
            }
        }
        f[i][j][l]=-1;
        return false;
    }

    private boolean check(int i, int j, int l) {
        int[] f=new int[26];
        int[] g=new int[26];
        for (int i1 = 0; i1 < l; i1++) {
            f[s1.charAt(i+i1)-'a']++;
            g[s2.charAt(j+i1)-'a']++;
        }
        for (int i1 = 0; i1 < 26; i1++) {
            if (f[i1]!=g[i1]){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new Solution87().isScramble("great","rgeat"));
    }
}
